\documentclass[11pt,letterpaper]{article}

\newcommand{\mytitle}{CS254 Homework 4}
\newcommand{\myauthor}{Kevin Lewi}
\date{February 10, 2012}

\usepackage{hwformat}

\begin{document}

\maketitle

\section*{Problem 1}

The idea we can use here is to show that we can make modifications to a graph 
such that if it does have a Hamiltonian cycle, it will have a lot of cycles, and 
if it does not have a Hamiltonian cycle, it will have \emph{much} fewer cycles.

Consider the following idea first: for an edge $e = (x,y)$, we can add three 
intermediate nodes $u$, $v$, and $z$ from $x$ to $y$ such that there are now 
exactly two paths from $x$ to $y$: $(x,u,z,y)$ and $(x,v,z,y)$. We can then 
repeat this augmenting paths process by adding vertices between $z$ and $y$. We 
can actually repeat this process a polynomial number of times, where if $k$ 
represents the number of times this augmenting step occurs, then we have created 
$2^k$ paths from $x$ to $y$.

Given an instance of directed Ham. cycle with a graph $G$, we construct a graph 
$H$ in the following manner: for each edge $e = (x,y)$, we run the augmenting 
process $n^2$ times in between $x$ and $y$, so that there are now $2^{n^2}$ 
paths within a single edge $e = (x,y)$. Thus, if $G$ contains a Hamiltonian 
cycle, there are $n$ edges on this cycle, and so there are $2^{n^3}$ cycles that 
we have just created in $H$ that correspond to this original Hamiltonian cycle.

Note that if $G$ does not have a Hamiltonian cycle, there can be at most $n! 
\cdot 2^{n^2(n-1)}$ cycles in $H$, since there are $n!$ ways of ordering the 
vertices and each cycle has size at most $n-1$, and we have run the augmenting 
procedure $n^2$ times for each edge. Note that this quantity is the same as $n! 
\cdot 2^{n^3 - n^2} = n! / 2^{n^2} \cdot 2^{n^3}$. Now, $n! \leq n^n \leq 
(2^n)^n = 2^{n^2}$, so that this quantity is less than $2^{n^3}$. We can even 
say that it is less than $1/2 \cdot 2^{n^3}$.

Thus, our reduction is as follows: given an instance of Hamiltonian cycle on 
$G$, construct $H$, and then approximate the number of cycles. If the 
approximation algorithm outputs an answer that is at least $1/2 \cdot 2^{n^3}$, 
output that there is a Ham. cycle, and otherwise, output No.

\section*{Problem 2}


\section*{Problem 3}

Let $C$ be a circuit for a problem in $P^{\sharp P}$. We will use 
$\mathcal{D}_n$ here in this case to represent the distribution over instances 
of the problem of length $n$, where $\mathcal{D}_n(x) = 1$ iff $C(x) = 1$ for 
some instance $x$ of the problem. We first show that any problem in $P^{\sharp 
P}$ is polytime sampleable. Then, by our assumption, we know that it must also 
be polytime computable.

But once we have determined that it is polytime computable, we can simply 
compare the outputs of $A(x)$ and $A(x-1)$ (where, $x-1$ represents the instance 
that appears lexicographically right before $x$), and if the outputs are 
different, then we know that instance $x$ has output $1$.


\end{document}
